#include<iostream>
#include<vector>
using namespace std;
//LeetCode 46 Permutations

vector<vector<int>> result;
vector<int> temp;
void backtrack(int n,int index, vector<int> nums, vector<bool>& used) 
{
    if(index > n)
    {
        for(auto& n : temp)
        {
            cout << n << " ";
        }
        cout << endl;
        result.push_back(temp);
        return;
    }
    for(int i = 0;i < n;++i)
    {
        if(!used[i])
        {
            temp.push_back(nums[i]);
            used[i] = true;
            backtrack(n,index+1,nums,used);
            used[i] = false;
            temp.pop_back();
        }
    }
}
vector<vector<int>> permute(vector<int>& nums) {
    int n = nums.size();
    vector<bool> used(n, false);
    backtrack(n,0,nums,used);
    return result;
}
int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result = permute(nums);
    for (auto& v : result) {
        for (auto& n : v) {
            cout << n;
        }
        cout << endl;
    }
    return 0;
}